/*
 * @lc app=leetcode.cn id=1143 lang=swift
 *
 * [1143] 最长公共子序列
 */

// @lc code=start
class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        let firstCharacters = Array(text1)
        let secondCharacters = Array(text2)
        let firstLength = firstCharacters.count
        let secondLength = secondCharacters.count
        
        var dp = [[Int]].init(repeating: [Int].init(repeating: 0, count: secondLength + 1), count: firstLength + 1)
        for i in 1...firstLength {
            for j in 1...secondLength {
                if firstCharacters[i - 1] == secondCharacters[j - 1] {
                    dp[i][j] = dp[i-1][j-1] + 1
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                }
            }
        }
        return dp[firstLength][secondLength]
    }
}

// @lc code=end

